package com.wfm.leetcode.editor.cn;

import com.wfm.common.ListNode;

public class BM13判断一个链表是否为回文结构O027 {
    public boolean isPalindrome(ListNode head) {
        if (head==null) return true;
        ListNode mid = getMid(head);
        ListNode reserve = reserve(mid.next);
        boolean res =  true;
        ListNode p1 = head;
        ListNode p2 = reserve;
        while (p2!=null){
            if(p1.val!=p2.val){
                res = false;
            }
            p1=p1.next;
            p2=p2.next;
        }
        return res;
    }

    ListNode getMid(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next!=null&&fast.next.next!=null){
            slow= slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
    public ListNode reserve(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur!=null){
            ListNode next = cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
}
